<?php


class SegmentTree
{
    private $data = [];
    private $tree = [];
    private $merge = null; //表示的是一个 节点操作的对象

    /**
     * 构造函数 初始化线段树
     * SegmentTree constructor.
     * @param array $arr
     */
    public function __construct(array $arr, $merge)
    {
        $this->merge = $merge;
        for ($i = 0; $i < count($arr); $i++) {
            $this->data[$i] = $arr[$i];
        }
        //若是静态语言需要开 4n 空间来表示 $this->tree

        //递归创建线段树
        $this->buildSegmentTree(0, 0, count($this->data) - 1);
    }

    public function query($qleft, $qright)
    {
        if ($qleft < 0 || $qright >= count($this->data) || $qright < $qleft) {
            echo "索引范围错误";
            exit;
        }
        return $this->recursionQuery(0, 0, count($this->data) - 1, $qleft, $qright);
    }

    /**
     * 递归查询区间
     * @param $left 当前节点区间左端值
     * @param $right 当前节点区间右端值
     * @param $qleft 需要查询的区间左端值
     * @param $qright 需要查询的区间右端值
     */
    private function recursionQuery($i, $left, $right, $qleft, $qright)
    {
        $mid = $left + ceil(($right - $left) / 2);//求区间中值向上取整
        //先处理满足区间条件的情况
        if ($qleft == $left && $qright == $right) { //查询左右端和当前节点左右端重合
            return $this->tree[$i];
        } elseif ($qright < $mid) { //查询左右端在中值左边，那么结果区间在左儿子树
            return $this->recursionQuery($this->leftSon($i), $left, $mid - 1, $qleft, $qright);
        } elseif ($qleft >= $mid) { //查询左右端在中值右边，那么结果区间在右儿子树
            return $this->recursionQuery($this->rightSon($i), $mid, $right, $qleft, $qright);
        } else { //中值在查询左右端中间 将区间分成两边，结果在左右儿子树上都有
            $leftSon = $this->recursionQuery($this->leftSon($i), $left, $mid - 1, $qleft, $mid - 1);
            $righttSon = $this->recursionQuery($this->rightSon($i), $mid, $right, $mid, $qright);
            return $this->merge->operate($leftSon, $righttSon);
        }
    }

    private function buildSegmentTree(int $i, int $left, int $right)
    {
        if ($left == $right) {
            $this->tree[$i] = $this->data[$left]; //处理递归到叶子节点时 并赋值最原始的 $data 对应的索引值
        } else {
            $leftSon = $this->leftSon($i); //左儿子索引
            $rightSon = $this->rightSon($i); //右儿子索引
            $mid = $left + ceil(($right - $left) / 2);//求区间中值
            $this->buildSegmentTree($leftSon, $left, $mid - 1); //递归左儿子树
            $this->buildSegmentTree($rightSon, $mid, $right); //递归右儿子树
            $this->tree[$i] = $this->merge->operate($this->tree[$leftSon], $this->tree[$rightSon]); //这里是根据业务来定节点需要存储的元素
        }
    }

    public function getSize()
    {
        return count($this->data);
    }

    public function get(int $index)
    {
        if ($index < 0 || $index >= count($this->data)) {
            echo "索引错误";
            exit;
        }
        return $this->data[$index];
    }

    /**
     * 获取某个节点儿子节点索引，若索引是从 i=0 开始的，左儿子 left(i) = 2*i+1
     * @param $i
     * @return int
     */
    private function leftSon($i): int
    {
        return $i * 2 + 1;
    }

    /**
     * 获取某个节点右儿子节点索引，若索引是从 i=0 开始的，右儿子 left(i) = 2*i+2
     * @param $i
     * @return int
     */
    private function rightSon($i): int
    {
        return $i * 2 + 2;
    }
}
